package com.leetcode.array_matrix;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author Dennis Li
 * @date 2020/10/19 17:18
 */
public class Trap_42 {

    public int trap(int[] height) {
        Deque<Integer> stack = new LinkedList<>();
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            // 当在首尾且高度为0的时候，不能接雨水
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                // 必须要在首尾之间
                int h = height[stack.pop()];
                if (stack.isEmpty())
                    break;
                int width = i - stack.peek() - 1;
                int min = Math.min(height[stack.peek()], height[i]);
                sum += width * (min - h);
            }
            stack.push(i);
        }
        return sum;
    }


    static class Solution {
        public int trap(int[] height) {
            int sum = 0;
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < height.length; i++) {
                while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                    int h = height[stack.pop()];
                    if (stack.isEmpty()) break;
                    int width = i - stack.peek() - 1;
                    // 想要做一个最小值的判定，有可能这个时候比height大
                    int min = Math.min(height[i], height[stack.peek()]);
                    sum += (min - h) * width;
                }
            }
            return sum;
        }
    }
}
